public class BinarySearch {
    public int mySqrt1(int x) {
        long[] nums = new long[x + 1];
        int i = 0;
        for (; (long)(i * i) <= (long)x; i++) {
            nums[i] = (long)(i * i);
        }
        int left = 0, right = i - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < (long)x) {
                left = mid + 1;
            } else if (nums[mid] == (long)x) {
                return mid;
            } else {
                right = mid - 1;
            }
        }
        return left - 1;
    }

    public int mySqrt2(int x) {
        if (x < 1) {
            return 0;
        }

        int left = 1, right = x;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            long num = (long)mid * (long)mid;
            if (num <= (long)x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
